//
// Created by wdq on 22-9-21.
//
#include <iostream>
#include <cstring>

using namespace std;


#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 100

template<typename ElemType>
struct SeqList {
    ElemType *data;
    int length;
    int capacity;

    /*!
     * 构造函数
     * @param capacity 初始化容量大小，不传默认为LIST_INIT_SIZE
     */
    explicit SeqList(int capacity = LIST_INIT_SIZE) {
        this->length = 0;
        this->capacity = capacity;
        this->data = new ElemType[capacity];
    }

    /*!
     * 析构函数
     */
    ~SeqList() {
        delete[]this->data;
    }

    virtual /*!
     *
     * @param index 索引
     * @return 值
     */
    ElemType get(int index) {
        if (index < 0 || index >= this->length)
            throw std::out_of_range("the index is not legal!");
        return this->data[index];
    }

    /*!
     * 扩容函数
     * @param targetCapacity 目标容量
     */
    void expansion(int targetCapacity = LIST_INCREMENT) {
        this->capacity = targetCapacity;
        auto *newData = new ElemType[this->capacity];
        delete[]this->data;
        //将原来的数据拷贝到新的地址
        memcpy(newData, this->data, this->length * sizeof(ElemType));
        this->data = newData;
    }

    /*!
     *
     * @param index 索引
     * @param value 要设置的值
     */
    void set(int index, ElemType value) {
        if (index < 0 || index >= this->length)
            throw std::out_of_range("the index is not legal!");
        this->data[index] = value;
    }


    /*!
     * 运算符重载,并返回真正的值，不返回拷贝的值
     * @param index
     * @return
     */
    ElemType &operator[](int index) {
        if (index < 0 || index >= this->length)
            throw std::out_of_range("the index is not legal!");
        return this->data[index];
    }

    /*!
     * 将元素加到最后
     * @param value
     */
    void push(ElemType value) {
        //判断容量是否够，不够就扩容，够就直接添加
        if (this->length < this->capacity) {
            this->data[this->length++] = value;
            return;
        }
        expansion(this->capacity + LIST_INCREMENT);
        this->data[length++] = value;
    }

    /*!
     * 删除最后一个元素
     * @return
     */
    ElemType pop() {
        if (this->isEmpty()) {
            throw std::out_of_range("there is no element in list!");
        }
        return this->data[--this->length];
    }

    /*!
     * 找到元素的位置，没有就返回-1
     * @param value
     * @return index
     */
    int find(ElemType value) {
        for (int i = 0; i < this->length; i++) {
            if (this->get(i) == value) {
                return i;
            }
        }
        return -1;
    }

    /*!
     * 删除指定位置的元素
     * @param index
     */
    void deleteElement(int index) {
        for (int i = index; i < this->length - 1; i++) {
            this->data[i] = this->data[i + 1];
        }
        this->length--;

    }


    /*!
     * 向指定位置插入元素
     * @param index
     * @param value
     */
    void insert(int index, ElemType value) {
        for (int i = this->length; i > index; i--) {
            this->data[i] = this->data[i - 1];
        }
        this->data[index] = value;
        this->length++;

    }


    /*!
     * 打印函数
     */
    void print() {
        for (int i = 0; i < this->length; i++) {
            std::cout << this->get(i) << " ";
        }
        std::cout << std::endl;
    }

    /*!
     * 判断数组是否为空
     * @return
     */
    bool isEmpty() {
        return this->length == 0;
    }


};

template<typename ElemType>
struct MinHeap : SeqList<ElemType> {
    MinHeap() : SeqList<ElemType>() {

    }

    int getParentIndex(int child) {
        if (child == 0 || child > this->length - 1) {
            return -1;
        }
        return (child - 1) >> 1;

    }

    void adjust(int i = 0) {
        while (i < this->length) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int j = i;
            if (left < this->length && this->data[left] < this->data[j]) {
                j = left;
            }
            if (right < this->length && this->data[right] < this->data[j]) {
                j = right;
            }
            if (i == j) break;
            swap(this->data[i], this->data[j]);
            i = j;

        }

    }


    void enqueue(ElemType e) {
        this->push(e);
        int index = this->length - 1;
        int parent = getParentIndex(index);
        while (parent != -1 && this->data[parent] > this->data[index]) {
            swap(this->data[parent], this->data[index]);
            index = parent;
            parent = getParentIndex(index);
        }


    }

    ElemType dequeue() {
        int temp = this->data[0];
        swap(this->data[0], this->data[this->length - 1]);
        this->pop();
        adjust();
        return temp;

    }

    ElemType get(int i) override {
        return this->data[i];
    }


};

void heapSort(int nums[], int length) {
    MinHeap<int> minHeap;
    for (int i = 0; i < length; i++) {
        minHeap.enqueue(nums[i]);
    }
    for (int i = 0; i < length; i++) {
        nums[i] = minHeap.dequeue();
    }


}

int main() {

    int nums[] = {2, 6, 1, 56, 25, 67, 89, 5, 3, 3};
    printf("nums: ");
    for (auto &i: nums) {
        printf("%-4d ", i);
    }
    printf("\n");
    heapSort(nums, sizeof(nums) / sizeof(int));
    printf("sorting..........................\n");
    printf("nums: ");
    for (auto &i: nums) {
        printf("%-4d ", i);
    }
    printf("\n");
    return 0;
}